package com.aikon.wht.paoshan.alg;

/**
 * 跳表.
 *
 * @author WANGHAITAO273
 */
public class PaoshanOfSkipList {

    public static class SkipList<T extends Comparable> {
        private Node<T> head;

        public void add(T val) {

        }

        public Node<T> get(T val) {
            if (head == null) {
                return null;
            }
            Node<T> cur = head;
            return get(val, cur);
        }

        private Node<T> get(T val, Node<T> cur) {
            Node<T> pre = findPre(val, cur);
            if (pre.val.equals(val)) {
                while (pre.forward != null) {
                    pre = pre.forward;
                }
                return pre;
            } else {
                if (pre.forward == null) {
                    return null;
                } else {
                    return get(val, pre.forward);
                }
            }
        }

        private Node<T> findPre(T val, Node<T> cur) {
            Node<T> pre = cur;
            while (cur.val.compareTo(val) < 0) {
                pre = cur;
                cur = cur.next;
            }
            return pre;
        }

        public static void main(String[] args) {

        }

    }

    public class Node<T> {
        private T val;

        private Node<T> next;

        private Node<T> forward;

    }
}

